package orTree;

import predicate.*;
import examSchedule.Environment;

import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Scanner;

import cpsc433.Pair;


public class Node {
	private Node parent;
	private List<Node> children;
	public int penalities;
	public List<Pair<Session, Lecture>> currentSchedule;
	public int depth;

	public static int numberOfNode = 0;

	public Node() {
		parent = null;
		children = new LinkedList<Node>();
		currentSchedule = new LinkedList<Pair<Session, Lecture>>();
		penalities = 0;
		depth = 0;
		numberOfNode++;
	}

	public Node(Node parent) {
		this.parent = parent;
		children = new LinkedList<Node>();
		currentSchedule = new LinkedList<Pair<Session, Lecture>>();
		Iterator< Pair<Session, Lecture> > iterator = parent.currentSchedule.iterator();
		penalities = parent.penalities;
		depth = parent.depth + 1;
		while (iterator.hasNext()) {
			currentSchedule.add(iterator.next());
		}

		numberOfNode++;
	}

	public void addPairSessionLecture(Session s, Lecture l) {
		Pair<Session, Lecture> pair = new Pair<Session, Lecture>(s,l);
		penalities = Constraints.getPenalities(currentSchedule, l, s, penalities);
		currentSchedule.add(pair);
	}

	public void setNewChildren(HashMap<String, Session> listSession, List<Lecture> listLectureOrTree) {		
		Lecture lecture = listLectureOrTree.get(depth);
		// For each session we verify if the lecture could be assigned.
		for (Entry<String, Session> e : listSession.entrySet()){
			// Verification of the hard constraints.
			if(Constraints.isRespectedHardConstraints(currentSchedule, lecture, e.getValue())) {
				Node newNode = new Node(this);
				newNode.addPairSessionLecture(e.getValue(), lecture);
				this.children.add(newNode);
			}
		}
	}

	public Node getBestChild() {
		if(children.size() == 0)
			return null;

		Node toReturn = children.get(0);
		int penalities = children.get(0).penalities;
		for(int i = 1; i < children.size(); i++) {
			if(children.get(i).penalities < penalities) {
				penalities = children.get(i).penalities;
				toReturn = children.get(i);
			}
		}
		return toReturn;
	}

	////////////////////////////////////////////////////////
	//
	//   Search in the or-tree
	//
	////////////////////////////////////////////////////////
	public static void search(Environment env, Long maxTime) {
		// Organize the order of the lecture
		List<Lecture> listLectureOrTree; 

		System.out.println("Order of the lecture for the Or-Tree : \n" +
				"1 \t No order \n" +
				"2 \t order by exam length \n" +
				"3 \t order by number of students \n" +
				"4 \t lecture group by Course, lecture with the longest length first \n : ");
		Scanner sc = new Scanner(System.in);

		int order = sc.nextInt();
		switch (order) {
		case 1:  listLectureOrTree = orderLectureOff(env);
		break;
		case 2:  listLectureOrTree = orderLectureByLength(env);
		break;
		case 3:  listLectureOrTree = orderLectureByStudent(env);
		break;
		case 4:  listLectureOrTree = orderLectureByLengthAndLecture(env);
		break;
		default: listLectureOrTree = orderLectureOff(env);
		break;
		}

		System.out.println("Level of the depth : ");
		int levelMax = sc.nextInt();
		int level = 0;

		// Initial node list
		List<Node> listNode = new LinkedList<Node>();
		List<Node> listLeaf = new LinkedList<Node>();

		// Initialization
		Node n = new Node();
		listNode.add(n);


		int bestPenalities = Integer.MAX_VALUE;


		long startTime = System.currentTimeMillis();

		while(!listNode.isEmpty() && (startTime + maxTime) > System.currentTimeMillis()) {
			// Selection of the node to visit
			Node toSee;
			// If there are a temporary Leaf, we take the best one
			if(!listLeaf.isEmpty()) {		
				toSee = listLeaf.get(0);
				listLeaf.clear();
				listNode.remove(toSee);

				if(toSee.penalities > bestPenalities) {
					toSee = listNode.get(0);
					listNode.remove(0);

					if(toSee.penalities > bestPenalities) {
						//System.out.println(toSee.penalities + " " + bestPenalities);
						break;
					}
				}
				// if it is a real leaf, save the solution
				if(toSee.depth == listLectureOrTree.size()) {
					if(toSee.penalities < bestPenalities) {
						env.solution.setSolved(true);
						env.solution.setSchedule(toSee.currentSchedule);
						env.solution.setGoodness(toSee.penalities);
						env.solution.setNumberOfNodeViewed(numberOfNode);
						env.solution.setTime(System.currentTimeMillis() - startTime);
						bestPenalities = toSee.penalities;
					}
				}
			} else {
				toSee = listNode.get(0);
				listNode.remove(0);

				if(toSee.penalities > bestPenalities) {
					//	System.out.println(toSee.penalities + " " + bestPenalities);
					break;
				}
			}

			if(toSee.depth < listLectureOrTree.size()) {
				//	System.out.println(toSee.depth + " / "+ listLectureOrTree.size() + " - Penalities :" + toSee.penalities);
				calculateChildNode(toSee, listNode, listLeaf, levelMax, level, env.listSession, listLectureOrTree);				
				level = 0;
			}
		}
		env.solution.setNumberOfNodeViewedFinal(numberOfNode);
	}

	public static void search2(Environment env, Long maxTime) {
		// Organize the order of the lecture
		List<Lecture> listLectureOrTree; 

		/*System.out.println("Order of the lecture for the Or-Tree : \n" +
				"1 \t No order \n" +
				"2 \t order by exam length \n" +
				"3 \t order by number of students \n" +
				"4 \t lecture group by Course, lecture with the longest length first \n : ");
		Scanner sc = new Scanner(System.in);
		int order = sc.nextInt();
		/*switch (order) {
		case 1:  listLectureOrTree = orderLectureOff(env);
		break;
		case 2:  listLectureOrTree = orderLectureByLength(env);
		break;
		case 3:  listLectureOrTree = orderLectureByStudent(env);
		break;
		case 4:  listLectureOrTree = orderLectureByLengthAndLecture(env);
		break;
		default: listLectureOrTree = orderLectureOff(env);
		break;
		}

		System.out.println("Nb of branch : ");
		int nbBranch = sc.nextInt();*/

		 listLectureOrTree = orderLectureByStudent(env);
		int nbBranch = 1;
		
		
		// Initial node list
		List<Node> listNode = new LinkedList<Node>();
		List<Node> listLeaf = new LinkedList<Node>();

		// Initialization
		Node n = new Node();
		listNode.add(n);
		


		int bestPenalities = Integer.MAX_VALUE;


		long startTime = System.currentTimeMillis();

		

		while((!listNode.isEmpty() || !listLeaf.isEmpty()) && (startTime + maxTime) > System.currentTimeMillis()) {
			Node[] toSee = new Node[10];

			// We select the N best current 
			if(!listLeaf.isEmpty()) {
				int i = 0;
				while(i < nbBranch && !listLeaf.isEmpty()) {
					Node node = listLeaf.get(0);
					listLeaf.remove(0);
					listNode.remove(node);

					// Is a node to see ?
					if(node.penalities < bestPenalities) {
						
						// if it is a real leaf, save the solution
						if(node.depth == listLectureOrTree.size()) {
							if(node.penalities < bestPenalities) {
								env.solution.setSolved(true);
								env.solution.setSchedule(node.currentSchedule);
								env.solution.setGoodness(node.penalities);
								env.solution.setNumberOfNodeViewed(numberOfNode);
								env.solution.setTime(System.currentTimeMillis() - startTime);
								bestPenalities = node.penalities;
							}
							
						} else { // Calculate is child
							toSee[i] = node;
							i++;
						}
					}
				}
				listLeaf.clear();
				for(int j = 0; j < i; j++) {
					//System.out.println(toSee[j].depth + " / "+ listLectureOrTree.size() + " - Penalities :" + toSee[j].penalities);

					calculateChildNode(toSee[j], listNode, listLeaf, 1, 0, env.listSession, listLectureOrTree);				
				}
			} else {			
				// Come back 
				int i = 0;
				while(i < nbBranch && !listNode.isEmpty()) {
					listLeaf.add(listNode.get(0));
					listNode.remove(0);
					i++;
				}
			}
		}
		env.solution.setNumberOfNodeViewedFinal(numberOfNode);
	}






	/*
	 * Calculate child on a depth of levelMax, and put the childreen in listNode
	 * 
	 */
	public static void calculateChildNode(Node n, List<Node> listNode, List<Node> listLeaf, int levelMax, int level, HashMap<String, Session> listSession, List<Lecture> listLectureOrTree) {
		if(level < levelMax) {
			level++;
			if(n.depth  < listLectureOrTree.size()) {
				n.setNewChildren(listSession, listLectureOrTree);
				// recurrence
				for(int i = 0; i < n.children.size(); i++) {
					calculateChildNode(n.children.get(i), listNode, listLeaf, levelMax, level, listSession, listLectureOrTree);
				}
			} else {
				add(listNode, n);
				add(listLeaf, n);
			}
		} else {
			add(listNode, n);
			add(listLeaf, n);
		}
	}


	/*
	 * And the node in the list, and conserve an order
	 */
	private static void add(List<Node> listNode, Node n) {
		if(listNode.isEmpty()) {
			listNode.add(n);
		} else {
			int i;
			for(i = 0; i < listNode.size(); i++) {
				if(listNode.get(i).penalities > n.penalities) {
					break;
				}
			}
			listNode.add(i, n);
		}
	}

	/**
	 * 
	 * OrderOff : no order
	 * @param env
	 * @return
	 */
	private static List<Lecture> orderLectureOff(Environment env) {
		List<Lecture> listLectureOrTree = new LinkedList<Lecture>();
		for (Entry<String, Lecture> e : env.listLecture.entrySet()){		
			listLectureOrTree.add(e.getValue());
		}
		return listLectureOrTree;
	}

	/**
	 * 
	 * OrderByLength : order Lecture by length
	 * @param env
	 * @return
	 */
	private static List<Lecture> orderLectureByLength(Environment env) {
		List<Lecture> listLectureOrTree = new LinkedList<Lecture>();
		for (Entry<String, Lecture> e : env.listLecture.entrySet()){		
			if (listLectureOrTree.isEmpty())
			{
				listLectureOrTree.add(e.getValue());
			}
			else
			{
				if (e.getValue().getLength() >= listLectureOrTree.get(0).getLength())
				{
					listLectureOrTree.add(0, e.getValue());
				}
				else if (e.getValue().getLength() <= listLectureOrTree.get(listLectureOrTree.size()-1).getLength())
				{
					listLectureOrTree.add(e.getValue());
				}
				else 
				{
					for (int i=0; i < listLectureOrTree.size()-1; i++)
					{				
						if (e.getValue().getLength() <= listLectureOrTree.get(i).getLength() &&
								e.getValue().getLength() >= listLectureOrTree.get(i+1).getLength())
						{	
							listLectureOrTree.add(i+1, e.getValue());
							break;
						}
					}
				}
			}
		}
		return listLectureOrTree;
	}

	/**
	 * 
	 * OrderByStudent : order Lecture by number of students
	 * @param env
	 * @return
	 */
	private static List<Lecture> orderLectureByStudent(Environment env) {
		List<Lecture> listLectureOrTree = new LinkedList<Lecture>();
		for (Entry<String, Lecture> e : env.listLecture.entrySet()){		
			if (listLectureOrTree.isEmpty())
			{
				listLectureOrTree.add(e.getValue());
			}
			else
			{
				if (e.getValue().getListStudent().size() >= listLectureOrTree.get(0).getListStudent().size())
				{
					listLectureOrTree.add(0, e.getValue());
				}
				else if (e.getValue().getListStudent().size() <= listLectureOrTree.get(listLectureOrTree.size()-1).getListStudent().size())
				{
					listLectureOrTree.add(e.getValue());
				}
				else 
				{
					for (int i=0; i < listLectureOrTree.size()-1; i++)
					{				
						if (e.getValue().getListStudent().size() <= listLectureOrTree.get(i).getListStudent().size() &&
								e.getValue().getListStudent().size() >= listLectureOrTree.get(i+1).getListStudent().size())
						{	
							listLectureOrTree.add(i+1, e.getValue());
							break;
						}
					}
				}
			}
		}
		return listLectureOrTree;
	}

	/**
	 * 
	 * OrderByLengthAndLecture : order Lecture by length and lecture
	 * @param env
	 * @return
	 */
	private static List<Lecture> orderLectureByLengthAndLecture(Environment env) {
		List<Lecture> listLectureOrTree = new LinkedList<Lecture>();
		boolean lectureExists = false;

		for (Entry<String, Lecture> e : env.listLecture.entrySet()){		
			if (listLectureOrTree.isEmpty())
			{
				listLectureOrTree.add(e.getValue());
			}
			else
			{
				for (int i=0; i < listLectureOrTree.size()-1; i++)
				{				
					if (listLectureOrTree.get(i).getName().equals(e.getValue().getName()) &&
							listLectureOrTree.get(i).getCourse().getName().equals(e.getValue().getCourse().getName()))
					{
						lectureExists = true;
						break;
					}
				}
				if (!lectureExists)
				{
					if (e.getValue().getListStudent().size() >= listLectureOrTree.get(0).getListStudent().size())
					{
						listLectureOrTree.add(0, e.getValue());
					}
					else if (e.getValue().getListStudent().size() <= listLectureOrTree.get(listLectureOrTree.size()-1).getListStudent().size())
					{
						listLectureOrTree.add(e.getValue());
					}
					else 
					{
						for (int i=0; i < listLectureOrTree.size()-1; i++)
						{				
							if (e.getValue().getListStudent().size() <= listLectureOrTree.get(i).getListStudent().size() &&
									e.getValue().getListStudent().size() >= listLectureOrTree.get(i+1).getListStudent().size())
							{	
								listLectureOrTree.add(i+1, e.getValue());
								break;
							}
						}
					}
				}

				else
				{					
					if (e.getValue().getListStudent().size() >= listLectureOrTree.get(0).getListStudent().size() &&
							listLectureOrTree.get(0).getName().equals(e.getValue().getName()) &&
							listLectureOrTree.get(0).getCourse().getName().equals(e.getValue().getCourse().getName())	)
					{
						listLectureOrTree.add(0, e.getValue());
					}
					else if (e.getValue().getListStudent().size() <= listLectureOrTree.get(listLectureOrTree.size()-1).getListStudent().size() &&
							listLectureOrTree.get(listLectureOrTree.size()-1).getName().equals(e.getValue().getName()) &&
							listLectureOrTree.get(listLectureOrTree.size()-1).getCourse().getName().equals(e.getValue().getCourse().getName()))
					{
						listLectureOrTree.add(e.getValue());
					}
					for (int i=0; i < listLectureOrTree.size()-1; i++)
					{
						if (e.getValue().getListStudent().size() <= listLectureOrTree.get(i).getListStudent().size() &&
								e.getValue().getListStudent().size() >= listLectureOrTree.get(i+1).getListStudent().size() &&
								listLectureOrTree.get(i).getName().equals(e.getValue().getName()) &&
								listLectureOrTree.get(i).getCourse().getName().equals(e.getValue().getCourse().getName()))
						{	
							listLectureOrTree.add(i+1, e.getValue());
							break;
						}
					}
				}
			}

			lectureExists = false;
		}
		return listLectureOrTree;
	}

}
